class Solution:
    def jump(self, nums: List[int]) -> int:
        l=len(nums)
        reach=[0]*l
        reach[0]=1
        for index,n in enumerate(nums):
            if reach[index]>0:
                for i in range(index,min(l,index+n+1)):
                    if reach[i]==0:
                        reach[i]=reach[index]+1
                    else:
                        reach[i]=min(reach[i],reach[index]+1)
        return reach[-1]-1


'''
超时
'''

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        maxPos, end, step = 0, 0, 0
        for i in range(n - 1):
            if maxPos >= i:
                maxPos = max(maxPos, i + nums[i])
                if i == end:
                    end = maxPos
                    step += 1
        return step
